package com.ddd.demo.lee.排序;

public class 插入排序 {

    public static void main(String[] args) {

        int[] arr = new int[]{1, 3, 2, 4, 5};

        insertSort(arr);

        System.out.println("排序后");

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    private static void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {

            for (int j = 0; j < i; j++) {
                if(arr[i] < arr[j]){
                    // 交换位置
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    // 从j+1到i的数据都需要往后面移一位
                    int k = j + 1;
                    while (k < i){
                        arr[k] = arr[k+1];
                        k++;
                    }
                }
            }

        }
    }

}
